//01背包问题
#include<bits/stdc++.h>
using namespace std;
int main()
{
	cout<<"capacity:";
	int V;
	while(cin>>V)
	{
		cout<<"object num:";
		int n;
		cin>>n;
		int *w=new int[n+1];//n种物体的价值
		int *v=new int[n+1];//n种物体的大小
		int *M=new int[n+1];//n种物体的大小
		v[0]=0;
		w[0]=0;
		M[0]=0;
		cout<<"object size:";
		for(int i=1;i<=n;i++)cin>>v[i];
		cout<<"object value:";
		for(int i=1;i<=n;i++)cin>>w[i];
		cout<<"object num:";
		for(int i=1;i<=n;i++)cin>>M[i];
		int **F=new int*[n+1];
		for(int i=0;i<=n;i++)
		{
			F[i]=new int[V+1];
			if(i==0)
			{
				for(int j=0;j<=V;j++)F[i][j]=0;
			}
			else 
			{
				for(int j=0;j<=V;j++)F[i][j]=INT_MIN;
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=V;j++)
			{
				//将当前号物体的大小与当前容量相处得出能够进i号物体的最大价值
				//若为完全背包问题，则int cpmin=j/v[i];
				int cpmin=min(M[i],j/v[i]);
				for(int k=0;k<=cpmin;k++)
				{
					int tmp=F[i-1][j-k*v[i]]+k*w[i];
					if(tmp>F[i][j])F[i][j]=tmp;
				}
			}
		}
		cout<<"max value:"<<F[n][V]<<endl;
		cout<<"capacity:";
	}
}